#leetcode题目99：恢复二叉搜索树
#难度：中等

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        self.pre = TreeNode(float("-inf"))
        self.first = None
        self.second = None
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            if self.first == None and self.pre.val >= root.val:
                self.first = self.pre
            if self.first and self.pre.val >= root.val:
                self.second = root
            self.pre = root
            inorder(root.right)
        inorder(root)
        self.first.val, self.second.val = self.second.val, self.first.val


#测试数据
def create_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

def inorder_traversal(root):
    result = []
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
    inorder(root)
    return result

#测试
#创建树: [1,3,None,None,2] (3和2被交换了)
root = create_tree([1, 3, None, None, 2])
print("恢复前的中序遍历:", inorder_traversal(root))

solution = Solution()
solution.recoverTree(root)
print("恢复后的中序遍历:", inorder_traversal(root))

